//
//  中缀表达式转后缀表达式并求值.cpp
//  408数据结构
//
//  Created by Cai Yuanhao on 2022/3/27.
//

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
//比较lhs的优先级是否不高于rhs，rhs表示栈顶的符号
bool priority(const char &lhs, const char &rhs)
{
    if (rhs == '(')//左括号在栈外优先级最高
        return false;
    if (lhs == '+' || lhs == '-')
        return true;
    if ((lhs == '*' || lhs == '/') && (rhs == '*' || rhs == '/'))
        return true;
    return false;
}
//将中缀表达式转换成后缀式（逆波兰表达式）
string exchange(const string &str)
{
    vector<char> vec;
    string res;
    stack<char> st;//操作符堆栈
    for (int i = 0; i < str.size(); ++i)
    {
        if (isdigit(str[i]))//如果是数字，直接输出到后序表达式中
        {
            vec.push_back(str[i]);
        }
        else//如果是符号,需要与栈顶的元素进行比较
        {
            if (st.empty() || str[i] == '(')//小括号在栈外优先级最高，直接压栈
                st.push(str[i]);
            else
            {
                if (str[i] == ')')//遇到右括号，则弹栈，直到遇到左括号，两者相互抵消
                {
                    while (!st.empty() && st.top() != '(')
                    {
                        vec.push_back(st.top());
                        st.pop();
                    }
                    st.pop();
                }
                else//遇到的是其他操作符
                {
                    if (priority(str[i], st.top()))//优先级比栈顶元素低
                    {
                        while (!st.empty())
                        {
                            vec.push_back(st.top());
                            st.pop();
                        }
                        st.push(str[i]);
                    }
                    else//优先级比栈顶元素高，压栈
                    {
                        st.push(str[i]);
                    }
                }
            }
        }
    }
    while (!st.empty())//如果堆栈不为空，则将其中的元素全部弹出
    {
        vec.push_back(st.top());
        st.pop();
    }
    for (auto v : vec)
        res += v;
    return res;
}

//以下是后缀表达式求值
//定义四则运算
int operate(int first, int second, char op)
{
    int res = 0;
    switch (op)
    {
        case '+':
            res = first + second;
            break;
        case '-':
            res = first - second;
            break;
        case '*':
            res = first*second;
            break;
        case '/':
            res = first / second;
            break;
        default:
            break;
    }
    return res;
}

int calculate(string input)
{
    stack<int> st;//操作数堆栈
    for (auto &s : input)
    {
        if (isdigit(s))//如果是数字就压栈
        {
            st.push(s - '0');
        }
        else//遇到字符就弹出两个操作数进行运算
        {
            int a = st.top();
            st.pop();
            int b = st.top();
            st.pop();
            st.push(operate(b, a, s));
        }
    }
    return st.empty() ? 0 : st.top();//最后的结果为栈顶元素
}
int main(int argc, char const *argv[])
{
    string str = "1+(3+4)*5-2";
    cout << exchange(str) << endl;
    cout << calculate(exchange(str)) << endl;
    string zhongzhui;
    cout<<"input";
    cin>>zhongzhui;
    cout<<zhongzhui<<endl;
    cout << exchange(zhongzhui) << endl;
    cout << calculate(exchange(zhongzhui)) << endl;
    return 0;
}
